1. Field of the Invention
The present invention relates to a compiler having a vector processing function and, more particularly to a vectorized checkup method for converting an array calculation in a loop processing step appearing in a source program into a vector calculation.
2. Description of the Related Art
In a data processing apparatus (computer) having a compiler including a vector processing function, when array calculations which can be vector-processed appear in a loop processing step in a source program upon execution of compile processing of the source program, this step is substituted by a vector calculation instruction (vectorized conversion processing), thereby increasing a vector processing speed.
For example, assume that a source program in the FORTRAN language describes a DO loop processing step having the following condition, i.e., an initial value [1] and an end value [N]. ##EQU1##
These program steps are substituted by the following vector calculations by vectorized conversion processing: EQU IX=(1:N) EQU A(IX)=B(IX)+C(IX)
The converted program steps as an intermediate text which has already been vectorized as described above are then optimized to generate object codes.
IX in the above equations represents an argument of a vector which changes between the initial value [1] to the end value [N], and is defined as one description element of a vector calculation formula. Therefore, for example, an expression A(IX) means that A(1), A(2), . . . , A(N) are vector-processed (simultaneously accessed) in turn for an array A.
According to the program description method described above, the array A need only be accessed according to a change range (1:N) of a control variable included in a DO loop, so that conventional equivalent processing using the DO loop an be easily vectorized.
However, a DO loop appearing in a program in, e.g., the FORTRAN language often has a more complex processing step (program) structure. For example, assume that a DO loop has a program structure including a plurality of (two) statements S1 and S2 as follows: ##EQU2##
In &lt;Example 2&gt;, if arrays B in the two statements S1 and S2 in the loop are vectorized (i.e., subjected to expression conversion) according to a dependency relation of their reference orders so that the vector processing can be executed in the order of the statement S1 and the statement S2, a solution different from a designed calculation result of the source program is undesirably obtained. In this case, therefore, the vectorized processing must be performed by replacing the order of statements as follows in consideration of a data reference relation (access order relation) of the two statements S1 and S2. EQU IX=(1:N) EQU E(IX)=B(IX+1)+D(IX) 2 EQU B(IX)=A(IX)+C(IX) S1
Furthermore, another case wherein a DO loop is given by a program description including two statements S1 and S2 is presented below. ##EQU3##
The reference relation between arrays A and B in the two statements S1 and S2 is called "data recursion". Therefore, it is impossible to obtain a solution of a correct vectorized program even if the two statements S1 and S2 are reordered anyway. Therefore, in consideration of the above case, the above input source program portion must be left as a scalar program which retains an original form (the order of steps).
As shown in the program description examples &lt;Examples 1 to 3&gt; of the three DO loops, in order to vectorize DO loop processing steps, the following two preprocessing operations are required:
(Processing 1): Analytical, judgment, and extraction processing for analyzing a data reference relation in a loop, judging to extract only a program portion (a set of statements) which can be vectorized, and leaving a program portion (a set of statements) which cannot be vectorized as a scalar program; and
(Processing 2): Reordering processing for appropriately reordering a plurality of statements according to a reference relation among the plurality of statements in order to guarantee correct execution of the vectorized processing.
In general vector calculations by a vector computer, the overall vector elements as calculation objects are simultaneously processed in principle. Therefore, a DO loop (intra-statement processing) which cannot simultaneously process vectors as calculation objects cannot be vectorized (converted) since it is against this principle.
More specifically, in the DO loop shown in &lt;Example 3&gt; described above, the statements S1 and S2 in the loop cannot uniquely determine a dependency relation of the data reference order in the same memory space by limiting it in one direction. That is, a plurality of arrays A and B may have opposite reference (dependency) relations as follows: EQU A:S1 .fwdarw.S2, B:S1.rarw.S2
As a result, since all vectors cannot be simultaneously processed (calculation simultaneity cannot be satisfied), it is impossible to vectorize (convert) program steps while keeping meanings of processing of the source program.
Therefore, in order to vectorize a program description of loop processing, the access order relation of data in the same memory space is checked, and checking results must be systematically judged. More specifically, whether or not the loop is against the above-mentioned "calculation simultaneity" as the basic principle of the vector calculations must be analyzed and judged beforehand. An idea which formulates a data access order relation in the same memory space is called "data dependence", as will be described below.
The "data dependence" includes the following three relations.
(1) "Flow Dependence"
In this dependence, the same memory position is accessed in the order of "definition".fwdarw."reference", and two statements S1 and S2 described in a loop have the following relations: ##EQU4##
(2) "Anti-dependence"
In anti-dependence, the same memory position is accessed in the order of "reference".fwdarw."definition", and two statements S1 and S2 described in a loop have the following relations: ##EQU5##
(3) "Output Dependence"
In this dependence, the same memory position is accessed in the order of "reference".fwdarw."reference", and two statements S1 and S2 described in a loop have the following relations: ##EQU6##
In vectorized processing for a DO loop in a source program, not only the order relation between "reference" and "definition" described above on a program but also data dependence regarding an iteration count associated with a loop index count of loop processing must be checked. For example, the following DO loop is assumed. ##EQU7##
Arrays A have the "flow dependence" in each iteration count of an iteration loop, and do not have data dependence throughout the iteration counts.
However, arrays A in other DO loops shown in the following two examples will be taken into account. ##EQU8##
In the above examples, the arrays A have the flow dependence in each iteration count of an iteration loop, and further have data dependence throughout the iteration counts. When the "flow dependence" is found from the program of the DO loop, data dependence throughout the iteration counts is checked, and the vectorized processing must be executed while distinguishing these dependence factors of the data dependence from each other. Therefore, Examples 4 and 5 described above are defined as follows:
The relation of the DO loop shown in &lt;Example 4&gt; is defined as "flow dependence having no iteration count dependence".
The relation of the DO loop shown in &lt;Example 5&gt; is defined as "flow dependence depending on the next iteration count".
The relation of the DO loop shown in &lt;Example 6&gt; is defined as "flow dependence depending on the previous iteration count".
The flow dependence has differences, as described above.
Note that data dependence is a relation for defining an execution order when statements in a loop are vectorized. Therefore, when a DO loop is vectorized, data dependence of all the data (scalar variables, 1-dimensional arrays, multiple dimensional arrays, and the like) appearing in the loop must be checked.
As a conventional data dependence analytical scheme associated with 1-dimensional array access in multiple loops, a scheme announced in the reference below is well known.
U. Banerjee;
"Time and Parallel Processor bounds for
Fortran-Like loops" IEEE trans.on Comp.
(Vol.c-28, No. 9, pp-660 to 670 (1979)
The data dependence analytical scheme (method) announced in the above reference analyzes "flow dependence " of a 1-dimensional array A in a DO loop as follows. In particular, statements included in multiple DO loops will be exemplified below. ##EQU9## where i1, i2, . . . , im in the program description of these loops represent control variables of each loop. Therefore, f and g are linear functions expressed by loop control variables. The following equations express argument functions in the loops of f and g, and are formulated as follows: ##EQU10##
Therefore, when kth and subsequent loops are parallelly executed, if statements S1 and S2 have the flow dependence at this level (this will be referred to as dependency of level k, the following conditions are satisfied:
&lt;&lt;Condition 1&gt;&gt;: gcd Test ##EQU11##
&lt;&lt;Condition 2&gt;&gt;: Banerjee Inequality
When q+=max{q,0} and q-=max{q,0} are defined, coefficients respectively satisfy the following inequality: ##EQU12##
In other words, the fact that "statements after the kth loop are parallelly executed" means that statements before the kth loop are sequentially executed. Therefore, the loop control variables of the functions f and g representing the statements S1 and S2 which are executed parallelly satisfy the following relations: EQU il=il', i2=i2', . . . , ik-1=ik-1'
This fact also implies that when this condition cannot be established, the dependence of the statements S1 and S2 need not be checked since they will never be parallelly executed.
In order to establish the "flow dependence" described above for the kth loop control variable, since the statement S2 must be executed after execution of the statement S1, the following relation is always satisfied: EQU ik.ltoreq.ik'
Therefore, to summarize the above-mentioned analysis contents, the following relation is established between loop variable vectors (il, i2, . . . , im) and (il', i2', . . . , im') when kth and subsequent loops are parallelly executed. ##EQU13##
Note that the mark "*" expresses that "the relation is unknown". An expression for expressing the relation among iteration counts of the loops is called a "dependency directional vector". A scheme for analyzing the dependence between the statements S1 and S2 according to the dependency directional vector and making a judgment for vectorized processing is called a "Banerjee's vectorized checkup system".
According to this "Banerjee's vectorized checkup system", dependence of 1-dimensional arrays having any access patterns in a source program can be extracted. However, when multiple dimensional arrays frequently appearing in DO loops are to be processed, the problem is how to extract the dependence.
More specifically, when data dependency analysis for DO loops which process multiple dimensional arrays is performed, the multiple dimensional arrays are normally converted to 1-dimensional images, and the 1-dimensional images are processed. If the multiple dimensional arrays can be converted to 1-dimensional images, data dependency analysis can be performed by directly adopting the "Banerjee's vectorized checkup system" described above.
Assume that the following DO loop is given. ##EQU14##
Arrays A in the statement No. 10 of the above statements are accessed in the following order: EQU A (i,j).fwdarw.A(i+(j-1)*10).fwdarw.A(i+10*j-10) EQU A(i-1,j+1).fwdarw.A(i+1+(j-1-1)*10).fwdarw.A(i+10*j-19)
Only when the multiple dimensional arrays are converted to 1-dimensional images, as described above, the "Banerjee's vectorized checkup system" can be adopted, and the data dependence of all the multiple dimensional arrays can be checked.
Preprocessing calculations for converting the multiple dimensional array data into 1-dimensional images are very complex and cumbersome. The converted 1-dimensional images require very complex argument expressions. Therefore, a calculation volume for analyzing the data dependence becomes very huge.
Furthermore, in order to develop multiple dimensional array data to 1-dimensional images, size information or size parameters of each dimension must be held for all the multiple dimensional arrays. Therefore, as a compiler of a program, its processing volume is considerably increased.
In the conventional vectorized checkup system described above, when processing statements of multiple dimensional arrays appear in DO loops of a source program, a reference format of each dimension of the multiple dimensional arrays is checked, and this reference format is developed to a format equivalent to 1-dimensional access (1-dimensional image) to perform a checkup operation associated with the data dependence. However, a calculation volume is increased accordingly, and a processing time required for compiling the program is much prolonged.